package dataStructure.linkedList.binaryTree;

import letcode.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description: 二叉树的层序遍历
 * @Date: 2020/4/22
 * @Author: 许群星
 */
public class AllorderTraversal {
    //按层访问
    List<List<Integer>> ans=new ArrayList<>();

    //队列 进行迭代
    public List<List<Integer>> allorder(TreeNode root){
        List<List<Integer>> ans=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null)
            return ans;
        queue.add(root);

        while (!queue.isEmpty()){
            //列表存储每一层的值
            List<Integer> temp=new ArrayList<>();
            for (int i = 0; i < queue.size(); i++) {
                TreeNode node=queue.poll();
                temp.add(node.val);
                if (node.left!=null)
                    queue.add(node.left);
                if (node.right!=null)
                    queue.add(node.right);
            }
            ans.add(temp);
        }
        return ans;
    }

    //递归方法
    public void helper(TreeNode node,int level){
        //从当前层开始，创建一个当前层的数组并放入二维数组res中
        if (ans.size()==level)
            ans.add(new ArrayList<Integer>());

        //将当前层的节点添加到对应的level的数组中
        ans.get(level).add(node.val);

        //处理下一层的子节点
        if (node.left!=null)
            helper(node.left,level+1);
        if (node.right!=null)
            helper(node.right,level+1);
    }
    public List<List<Integer>> allorder_diedai(TreeNode root){
        if (root==null)
            return ans;
        helper(root,0);
        return ans;
    }
}
